//
//  Problem148.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/26.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 148. 排序链表 中等

 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
  
 示例 1：
     输入：head = [4,2,1,3]
     输出：[1,2,3,4]
 示例 2：
     输入：head = [-1,5,3,4,0]
     输出：[-1,0,3,4,5]
 示例 3：
     输入：head = []
     输出：[]
  
 提示：
 链表中节点的数目在范围 [0, 5 * 104] 内
 -105 <= Node.val <= 105
 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 */
class Problem148: NSObject {
    
    /*
     思路：
     1: 每次折半，然后对这2个队列都递归进行sortList
     2: 排好序后队列，再进行合并
     */
    func sortList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        // 折半：快慢指针
        var slow = head, fast = head
        var last: ListNode? = nil
        while fast != nil {
            last = slow
            slow = slow?.next
            fast = fast?.next?.next
        }
        last?.next = nil
        // 排序后，合并
        return merge(sortList(head), sortList(slow))
    }
    
    /*
     思路：没有实现
     1: 将链表分割成每个长度都为1的子链表
     2: 每2个相邻的子链表进行合并，直到合并成一个链表
     */
    func sortList2(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        // 1: 求出链表的长度
        var first = head
        var length = 0
        while first != nil {
            length += 1
            first = first?.next
        }
        
        var subLength = 1
        while subLength < length {
            
            subLength <<= 1
        }
        
        return head
    }
    
    func merge(_ first: ListNode?, _ second: ListNode?) -> ListNode? {
        if first == nil {
            return second
        } else if second == nil {
            return first
        } else if first!.val <= second!.val {
            first?.next = merge(first?.next, second)
            return first
        } else {
            second?.next = merge(first, second?.next)
            return second
        }
    }
}
